package datastructure.sort;

import java.util.Arrays;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020-08-24 16:28
 */
public class MergeSort {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{34, 235, 1, 4, 52, 574, 7, 21, 1};
        mergeSort(arr);
        Arrays.stream(arr).forEach(System.out::println);

    }

    private static void mergeSort(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }
        Integer[] temp = new Integer[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void mergeSort(Integer[] arr, Integer[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr,temp,left,mid);
            mergeSort(arr,temp,mid+1,right);
            merge(arr,temp,left,mid+1,right);
        }
    }

    private static void merge(Integer[] arr, Integer[] temp, int left, int rightStart, int rightEnd) {
        int leftEnd=rightStart-1;
        int length=rightEnd-left+1;

        int curIndex=left;
        while (left <= leftEnd && rightStart<=rightEnd){
            if (arr[left]<arr[rightStart]){
                temp[curIndex++]=arr[left++];
            }else {
                temp[curIndex++]=arr[rightStart++];
            }
        }
        while (left<=leftEnd){
            temp[curIndex++]=arr[left++];
        }
        while (rightStart<=rightEnd){
            temp[curIndex++]=arr[rightStart++];
        }

        for (int i = 0; i < length; i++,rightEnd--) {
            arr[rightEnd]=temp[rightEnd];
        }
    }


    private static void mergeSortBottom(Integer[] arr, Integer[] temp) {
        int N = arr.length;
        for (int gap = 1; gap < N; gap *= 2) {

            for (int i = 0; i < N - gap; i += gap * 2) {
                int right = Math.min(N - 1, i + gap * 2 - 1);
                merge(arr, temp, i, i + gap, right);
            }
        }
    }


}
